There are many methods of rendering grey images on an output device. One such example is error diffusion. Error diffusion can render complex images that contain a mixture of text and picture reasonably well. The utilization of error diffusion eliminates the need to have image segmentation to separate the text from the picture so that the picture aspect of the document can be screened and the text aspect of the document can be threshold.
In a typical error diffusion binarization circuit, a modified video signal is fed to a comparator which compares the modified video signal to a threshold value. The comparator outputs a logic one when the modified video signal has a value greater than or equal to the threshold value and outputs a logic zero when the modified video signal has a value less than the threshold value. Depending on whether the rendering device connected to this error diffusion binarization circuit is a write white system or a write black system, the logic value of the output from the comparator will cause the rendering device to produce a pixel or not.
In addition to producing the binary value for the rendering device, the comparator produces an error value. The error value is the modified video signal value when the modified video signal has a value less than the threshold value, or the error value is equal to the modified video signal value minus the maximum video value when the modified video signal has a value greater than or equal to the threshold value. The error is diffused to downstream pixels, the next pixel in the same scanline and pixels in the next scanline. This error is then accumulated for each pixel such that when a particular pixel is to be processed by the error diffusion binarization circuit, the accumulated error value for the particular pixel is added to the incoming video signal corresponding to the particular pixel to produce the modified video signal being fed into comparator.
One problem associated with the utilization of error diffusion in rendering an image on a document is the occurrence of periodically repeating patterns. These patterns occur most notably at the grey levels of 85, 128, and 170 when an 8-bit data word is utilized to represent the grey level of the image data. For example, when the grey level input is 128, the binarized image can alternate between a checkerboard pattern and a vertical line pattern. Depending on the printer spot size and the grey level at which the spot was mapped, the vertical line pattern can appear lighter than the checkered board pattern, thereby producing a undesired artifact.
The idea of dithering or adding threshold perturbations to defeat visual artifacts of a regular and deterministic nature has been utilized in the prior art. For example, in the article “Digital Halftoning” by Robert Ulichney, it was proposed to add random noise, across the entire image, to the elements of the error weights or to the threshold to defeat the visual artifacts discussed above However, by adding noise to all parts of an image tends to degrade the image and will also destroy the dot pattern established in the highlight and shadow areas.
Conventionally, error diffusion systems perturbed a threshold relationship between a modified video image signal and a threshold signal by adding random noise to an error diffusion modified video or image signal in an error diffusion binarization system. In such systems, a random noise generator produces a random noise signal which is added to the error diffusion modified image signal. The random noise produced by the noise generator is a function of the grey level of the image to be threshold.
More specifically, if the grey level to be threshold represents either 128, 85, or 64, when utilizing an 8-bit data word to represent a grey level of the image data, the random noise generator will produce some random noise level which will be added to the image or video signal. The modified video or image signal is then binarized by a comparator circuit. The comparator circuit compares the modified video or image signal with a threshold value. If the modified video or image signal is greater than or equal to the threshold value, the comparator outputs a logical value indicating that the pixel is ON or if the modified video or image signal is less than the threshold value, the comparator circuit outputs a logical value representing that the pixel is OFF. An error is generated from this binarization process wherein this error is diffused to adjacent pixels utilizing any conventional error diffusion process.
This conventional noise perturbation process requires additional hardware or processing to generate the noise.
Alternatively, conventional error diffusion systems have also perturbed a threshold relationship between a modified video image signal and a threshold signal by using deterministic bit-flipping. In this conventional system, the thresholding process includes not only a minimum below which no dot is printed, but also a region above the threshold for which no dot is printed. The extra region is adjusted based on input level in order provide an appropriate amount of effect to break up the undesirable limit cycles.
This conventional bit-flipping perturbation process does not completely break-up the alternating patterns in the regions.